1. Field of the Invention
This invention relates generally to a method and apparatus for estimating the displacement and/or velocity of moving objects in television scenes or other picture sequences.
2. Description of Prior Art
Velocity and displacement estimation has been found to be useful in many applications including tracking and surveillance systems, evaluation of photographs taken from satellites, and in efficient coding of moving picture sequences for transmission and/or storage. One technique for measuring velocity is described in the context of a predictive video encoder in U.S. Pat. No. 3,632,865 issued to B. G. Haskell et al on Jan. 4, 1972. In that patent, the intensity of a particular picture location in a present frame is correlated with the intensity of a series of displaced picture locations in a previous frame, using a series of correlators. The correlator outputs are then integrated as the interframe intensity correspondence between other moving locations in the picture are evaluated. This approach to velocity determination proved cumbersome, in that many multiplications were required for each moving picture element. For example, if it were desired to determine velocity in the range of 0-4 pels per frame (pef) with an accurancy of 0.25 pef, a moving area correlation coefficient would be needed for each of the 10891/4 element possible displacements. Obviously, greater precision or a larger velocity range would require even larger processing capability.
A significant reduction in the number of computations required in the Haskell et al technique was enabled by a velocity estimation scheme described in U.S. Pat. No. 3,890,462 issued to J. O. Limb and J. A. Murphy on June 17, 1975. This scheme is based upon a recognition that the amount of frame difference signal (difference in intensity of a particular location in a picture from one frame to the next) generated by a moving object is a function of its speed and also of the size of the object and the amount of detail it contains. Furthermore, since size and detail are related to the amount of the element or line difference signal (difference in intensity between two particular locations in the same picture frame) generated by the object, an estimate of speed which is largely independent of size and detail can be obtained by normalizing the frame difference by the element or line difference.
Mathematically, the displacement calculation described by Limb and Murphy (for the horizontal or x direction) is given by ##EQU1## where FDIF is the frame difference, EDIF is the element difference, and the summation is carried over those elements in the picture for which FDIF is above a threshold value, indicating moving area. To calculate .DELTA.y, (displacement in the vertical direction) a corresponding computation is made using line difference LDIF rather than element difference EDIF. Naturally, speed or velocity can be calculated from the appropriate vector combinations of .DELTA.x, .DELTA.y and .DELTA.t.
While the Limb-Murphy technique resulted in fewer calculations than are required in the Haskell invention, it was based upon a simplification of a Taylor series expansion which assumed that .DELTA.x was small. However, when .DELTA.x is large, the Taylor's approximation becomes inaccurate, seriously degrading the displacement estimate. Also, the technique sometimes provides unsatisfactory results in scenes with multiple moving objects.
In view of the foregoing, it is the broad object of the present invention to provide means and a method for more accurately determining the displacement and/or velocity of moving objects in video scenes or the like. The technique must be adaptable to pictures with regions of differing movement, and must be capable of implementation in a manner that is not unduly complex or expensive.